/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package classes;

import java.util.ArrayList;


/**
 *
 * @author Filippo
 */
public class quaternarytree {
    
    public int k = 0;
    public int numpoints = 0;
    public int numbuckets = 0;
    public ArrayList <ArrayList<vertice>> buckets = new ArrayList<ArrayList<vertice>>();
    public ArrayList <ArrayList<quadtreenode>> treelevels = new ArrayList<ArrayList<quadtreenode>>();
    public quadtreenode rootnode = new quadtreenode();
    public int numrows;
    public vertice p1 = new vertice();
    
    public quaternarytree(ArrayList<vertice> generators, vertice p1) {
    createtree(generators,p1);    
    }

    public void createtree(ArrayList<vertice> generators, vertice p1) {
        
        this.numpoints = generators.size();
        definek();
        addpointstobuckets(generators);
        
        this.rootnode.nodetypes = nodelabels.ROOT_NODE;
        this.rootnode.addgenerator(p1);
        
        
        buildtree(this.k, this.rootnode, 0, this.numrows - 1, 0, this.numrows - 1);
        
        
    }

    public void definek() {
        
        this.k = (int) Math.round(Math.log((this.numpoints)/Math.log(4)));
        this.numbuckets =(int) Math.pow(4, this.k);
        this.numrows =(int) Math.sqrt(this.numbuckets);
        
        this.treelevels.ensureCapacity(k+1);
        for(int i=0; i<this.k; i++){
        
            this.treelevels.add(i,new ArrayList<quadtreenode>());
        }
        
        
        
    }

    public void addpointstobuckets(ArrayList<vertice> generators) {
        int r;
        int c;
        int index;
        int k2 =(int) Math.pow(2, this.k);
        int n = generators.size();
        vertice g;
        
        int maximum = k2 + (k2 * this.numrows);
        
        for (int i =0; i<maximum; i++){
        
            this.buckets.add(i, new ArrayList <vertice>());
        }
        
        for (int i=0; i<n; i++){
        
            g = generators.get(i);
            
            g.index = i;
            
            float x; float y;
            if (g.x == 1) x =(float) 0.999999;
            else x = g.x;
            
            if (g.y == 1) y =(float) 0.999999;
            else y = g.y;
            
            r =(int) (k2 * y) ;
            c =(int) (k2 * x) ;
            
            index = c + (r * this.numrows);
            /*
            if ( this.buckets.size() < index )
                this.buckets.ensureCapacity(index+10); 
            
            if (this.buckets.get(index) == null)
                this.buckets.set(index, new ArrayList<vertice>());
            */
            this.buckets.get(index).add(generators.get(i));
            
            
            
            
        }
        
    }

    public void buildtree(int kin, quadtreenode n, int rstart, int rend, int cstart, int cend) {
        
        if(kin>0){
            quadtreenode newnode;
            int divider1 = (int) (rstart + ((rend - rstart) / 2.0));
            int divider2 = (int) (cstart + ((cend - cstart) / 2.0));
            
            for (int i=0; i<4; i++){
            
                newnode = new quadtreenode();
                
                switch(i){
                    
                    case 0:
                        n.topleft = newnode;
                        newnode.parentnode = n;
                        buildtree(kin - 1, newnode, rstart, divider1, cstart, divider2);
                        break;
                        
                    case 1:
                        n.topright = newnode;
                        newnode.parentnode = n;
                        buildtree(kin - 1, newnode, rstart, divider1, divider2 + 1, cend);
                        break;
                        
                    case 2:
                        n.bottomleft = newnode;
                        newnode.parentnode = n;
                        buildtree(kin - 1, newnode, divider1 + 1, rend, cstart, divider2);
                        break;
                        
                    case 3:
                        n.bottomright = newnode;
                        newnode.parentnode = n;
                        buildtree(kin - 1, newnode, divider1 + 1, rend, divider2 + 1, cend);
                        break;
                }
                
                int idx = Math.abs(kin - k);
                this.treelevels.get(idx).add(newnode);
                
            }
        }
        
        else {
        
            int index = (int) (cstart + (rstart * this.numrows));
            n.nodetypes = nodelabels.LEAF_NODE;
            n.setgenerators(this.buckets.get(index));
            
            if(!(this.buckets.get(index).isEmpty()))
                populateparentnodes(n, this.buckets.get(index).get(0));
        }
        
    }

    public void populateparentnodes(quadtreenode child, vertice g) {
        
        quadtreenode parent = child.parentnode;
        int count = parent.getgeneratorcount();
        if((parent.nodetypes != nodelabels.ROOT_NODE) && (count==0)){
        
            parent.addgenerator(g);
            populateparentnodes(parent, g);
        }
    }
    
    public int levelcount() {return this.k;}
    
    public ArrayList <quadtreenode> getlevel(int i){
    
        if((i<0) || (i>(this.k - 1))) return null;
        
        else return this.treelevels.get(i);
    }
    
    public quadtreenode getrootnode() { return this.rootnode;}
    
    
    
}
